#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<string>
#define HuffmanCode char**
typedef struct 
{
	int weight;
	int parent,lch,rch;
}HTNode,*HuffmanTree;

void Treeselect(HuffmanTree &HT,int n,int &s1,int &s2)
{
	int m = 0;
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0)
		{
			m++;
		}
	}
	int s = 1;
	int* nHT = new int[m+1];
	for (int i = 1; i <= n; i++)
	{
		if(HT[i].parent == 0)
			nHT[s++] = HT[i].weight;
	}
	for (int i = 1; i <= m-1; i++)
	{
		for (int j = 1; j <= m - i; j++)
		{
			if (nHT[j] > nHT[j + 1])
			{
				int a = nHT[j];
				nHT[j] = nHT[j + 1];
				nHT[j + 1] = a;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (s1 <= n && HT[s1].weight == HT[i].weight)
		{
			s2 = i;
			continue;
		}
		if (s1 != 0 && s2 != 0)
		{
			break;
		}
		if (HT[i].parent==0&&HT[i].weight == nHT[1])
			s1 = i;
		else if (HT[i].parent == 0 && HT[i].weight == nHT[2])
			s2 = i;
	}
	delete[] nHT;
}
void CreateHuffmanTree(HuffmanTree &HT,int n,int arr[])
{
	if (n <= 1)
		return;
	int m = 2 * n - 1;
	HT = new HTNode[m + 1];
	for (int i = 1; i <= m; i++)
	{
 		HT[i].lch = 0;
		HT[i].parent = 0;
		HT[i].rch = 0;
	}
	for (int i = 1; i <= n; i++)
	{
		HT[i].weight=arr[i];
	}
	for (int i = n + 1; i<= m; i++)
	{
		int s1=0;
		int s2 =0;
		Treeselect(HT, i - 1, s1, s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lch = s1;
		HT[i].rch = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}
void CreateHuffmanCode(HuffmanTree &HT, HuffmanCode &HC, int n)
{
	HC = new char*[n+1];
	char* cd = new char[n];
	cd[n - 1] = '\0';
	for (int i = 1; i <= n; i++)
	{
		int start = n - 1;
		int c = i;
		int f = HT[i].parent;
		while (f)
		{
			--start;
			if (HT[f].lch == c)
				cd[start] = '0';
			else
				cd[start] = '1';
			c = f;
			f = HT[f].parent;
		}
		HC[i] = new char[n - start];
		strcpy(HC[i], &cd[start]);
	}
	delete cd;
}
int main()
{
	HuffmanTree HT;
	int arr[9] = {0,5,29,7,8,14,23,3,11};
	int n = 8;
	HuffmanCode HC;
	CreateHuffmanTree(HT,n,arr);
	cout << HT[14].lch << endl;
	CreateHuffmanCode(HT,HC, n);
	cout << HC[1] << endl;
	return 0;
}